package end;

import java.io.File;
import java.io.IOException;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Vector;

import javax.swing.tree.DefaultMutableTreeNode;

import unitrans.Transformer;
import weightingscheme.WeightingScheme;

import comparisonmethod.ComparisonMethod;

public class END {

    // Vector of transformer names
    private Vector<String> transformers;

    // Vector of comparison method names
    private Vector<String> methods;

    // Vector of weighting scheme names
    private Vector<String> schemes;

    /**
     * Create the list of transformers, comparison methods, and weighting
     * schemes included in the END distribution package.
     */
    public END() {

        // All names are case sensitive.

        // Transformers included with the END distribution package.
        // If more transformers are added to the unitrans package, they need to
        // be added here also.
        transformers = new Vector<String>();
        transformers.add("RSF2SIL");
        transformers.add("SIL2RSF");
        transformers.add("NESTED2RSF");
        transformers.add("RSF2NESTED");

        // Comparison methods included with the END distribution package.
        // If more comparison methods are added to the comparisonmethod package,
        // they need to be added here also.
        methods = new Vector<String>();
        methods.add("MoJo");

        // Weighting schemes included with the END distribution package.
        // If more weighting schemes are added to the weightingscheme package,
        // they need to be added here also.
        schemes = new Vector<String>();
        schemes.add("FirstElement");
        schemes.add("LastElement");
        schemes.add("AllElements");
        schemes.add("UpElements");
        schemes.add("DownElements");
    }

    public static void main(String[] args) {

        // END initialization.
        END end = new END();

        // The final result.
        double result = 0;

        /*
         * END needs minimum five command line arguments: input file1, input
         * file2, weighting scheme, comparison method, and comparison format.
         */
        if (args.length < 5)
        {
            System.out.println("Incorrect usage: END requires at least 5 arguments!");
            System.out.println("Usage: java end.END dec1 dec2 scheme method format [options]");
            System.out.println("  dec1 - The first of the two hierarchical decompositions");
            System.out.println("  dec2 - The second of the two hierarchical decompositions");
            System.out.println("  scheme - The weighting scheme to be used");
            System.out.println("    Known Weighting Schemes: " + end.schemes);
            System.out.println("  method - The comparison method to be used");
            System.out.println("    Known Comparison Methods: " + end.methods);
            System.out.println("  format - The name of the format that the comparison method uses");
            System.out.println("    Known Format Transformers: " + end.transformers);
            return;
        }

        // Input filenames must include an extension.
        if ((args[0].lastIndexOf(".") == -1) || (args[1].lastIndexOf(".") == -1))
        {
            System.out.println("Incorrect usage: input file names must include an extension!");
            return;
        }

        // Weighting scheme.
        String scheme = args[2];

        // Comparison method.
        String method = args[3];

        // The format that the comparison method uses (not case sensitive)
        String format = args[4];

        /*
         * Comparison options: They are not required to execute the comparison
         * method.
         */
        String options = "";
        for (int i = 5; i < args.length; i++)
        {
            options = options + args[i] + " ";
        }

        /*
         * Extract the file name and the file extension from the input files.
         */
        File in1 = new File(args[0]);
        String fileName1 = in1.getPath();
        String fileFormat1 = fileName1.substring(fileName1.lastIndexOf(".") + 1);
        String baseName1 = (in1.getName()).substring(0, (in1.getName()).lastIndexOf("."));

        File in2 = new File(args[1]);
        String fileName2 = in2.getPath();
        String fileFormat2 = fileName2.substring(fileName2.lastIndexOf(".") + 1);
        String baseName2 = (in2.getName()).substring(0, (in2.getName()).lastIndexOf("."));

        /*
         * rsf1 and rsf2 are rsf files to be transformed into trees. If the
         * input file is not an rsf file, a temporary rsf file is created in the
         * current directory. It has the following naming convention: "input
         * file1 name" + "input file2 name" + "_1.rsf" "input file1 name" +
         * "input file2 name" + "_2.rsf" If the input file is already an rsf
         * file, no transformation is needed and no temporary file is created.
         * (rsf1 == pathName1) (rsf2 == pathName2)
         */
        String rsfInput1 = null;
        String rsfInput2 = null;

        if (fileFormat1.equalsIgnoreCase("rsf")) rsfInput1 = fileName1;
        else rsfInput1 = baseName1 + baseName2 + "_1.rsf";

        if (fileFormat2.equalsIgnoreCase("rsf")) rsfInput2 = fileName2;
        else rsfInput2 = baseName1 + baseName2 + "_2.rsf";

        /*
         * tmp1 and tmp2 are temporary rsf files to be created by transforming a
         * level tree from NDVs into an rsf file. It has the following naming
         * convention: "input file1 name" + "_tmp1.rsf" "input file2 name" +
         * "_tmp2.rsf"
         */
        String tmp1 = baseName1 + "_tmp1.rsf";
        String tmp2 = baseName2 + "_tmp2.rsf";

        /*
         * compare1 and compare2 are two files to be compared by the comparison
         * method. If the comparison format is not rsf, transform the two
         * temporary rsf files (tmp1, tmp2) into the comparison format. It has
         * the following naming convention: "input file1 name" + "_tmp1.format"
         * "input file2 name" + "_tmp2.format" If the comparison format is rsf,
         * no transformation is needed and no temporary file is created.
         * (compare1 == tmp1) (compare2 == tmp2)
         */
        String compare1 = null;
        String compare2 = null;

        if (format.equalsIgnoreCase("rsf"))
        {
            compare1 = tmp1;
            compare2 = tmp2;
        }
        else
        {
            compare1 = baseName1 + "_tmp1" + "." + format;
            compare2 = baseName2 + "_tmp2" + "." + format;
        }

        try
        {
            // Transform input files into temporary rsf files.
            end.transformTwoFiles(fileName1, rsfInput1);
            end.transformTwoFiles(fileName2, rsfInput2);

            // Transform rsf files into trees.
            DefaultMutableTreeNode tree1 = end.transformRSFToTree(rsfInput1);
            DefaultMutableTreeNode tree2 = end.transformRSFToTree(rsfInput2);

            // Create nested decomposition vectors (NDV) from trees.
            Vector<DefaultMutableTreeNode> ndv1 = end.getNDV(tree1);
            Vector<DefaultMutableTreeNode> ndv2 = end.getNDV(tree2);

            // Even the size of two NDVs.
            DefaultMutableTreeNode treeAppend = null;
            int numAppend = Math.abs(ndv1.size() - ndv2.size());
            if (numAppend != 0)
            {
                if (ndv1.size() < ndv2.size())
                {
                    treeAppend = ndv1.lastElement();
                    for (int i = 0; i < numAppend; i++)
                        ndv1.add(treeAppend);
                }
                else
                {
                    treeAppend = ndv2.lastElement();
                    for (int i = 0; i < numAppend; i++)
                        ndv2.add(treeAppend);
                }
            }

            // The size of NDV.
            int ndvSize = ndv1.size();

            // Create a similiarity vector (sv) with the same size as NDV.
            Vector<Double> sv = new Vector<Double>(ndvSize);

            for (int i = 0; i < ndvSize; i++)
            {

                /*
                 * First transform level tree1 into the temporary rsf file
                 * (tmp1).
                 */
                DefaultMutableTreeNode levelTree1 = ndv1.elementAt(i);
                levelTree1.setUserObject(tmp1);
                end.transformTreeToRSF(levelTree1);

                /*
                 * Second transform level tree2 into the temporary rsf file
                 * (tmp2).
                 */
                DefaultMutableTreeNode levelTree2 = ndv2.elementAt(i);
                levelTree2.setUserObject(tmp2);
                end.transformTreeToRSF(levelTree2);

                /*
                 * Transform (tmp1, tmp2) into the format accepted by the
                 * comparison method. If the comparison method requires rsf
                 * format, no transformation occurs.
                 */
                end.transformTwoFiles(tmp1, compare1);
                end.transformTwoFiles(tmp2, compare2);

                /*
                 * Compare (compare1, compare2) and put the result into the
                 * similarity vector.
                 */
                sv.add(end.compareTwoFiles(method, compare1, compare2, options));
            }

            System.out.println(sv);

            /*
             * Apply the weighting scheme to the similarity vector (sv) to
             * obtain the final result.
             */
            result = end.weightAVector(scheme, sv);

        }
        catch (Exception e)
        {
            // Print the specific error message for the exception.
            System.out.println(e.getMessage());
            // Print the cause of the exception.
            System.out.println(e.getCause());
            // Set the final result to -1 to indicate error.
            result = -1;
        }

        // Remove the two temporary files (compare1, compare2).
        File remove1 = null;
        File remove2 = null;

        if (!format.equalsIgnoreCase("rsf"))
        {
            remove1 = new File(compare1);
            if (remove1.exists()) remove1.delete();
            remove2 = new File(compare2);
            if (remove2.exists()) remove2.delete();
        }

        // Remove the two temporary rsf files (tmp1, tmp2).
        remove1 = new File(tmp1);
        remove2 = new File(tmp2);

        if (remove1.exists()) remove1.delete();
        if (remove2.exists()) remove2.delete();

        // Remove the two temporary files (rsf1, rsf2).
        if (rsfInput1 != fileName1)
        {
            remove1 = new File(rsfInput1);
            if (remove1.exists()) remove1.delete();
        }

        if (rsfInput2 != fileName2)
        {
            remove2 = new File(rsfInput2);
            if (remove2.exists()) remove2.delete();
        }

        System.out.println("The result is " + result + ".");

        return;
    }

    /**
     * Transform the input decomposition file (in) into another format
     * decomposition file (out). The transformer class is named "input file
     * format uppercase" + 2 + "output file format uppercase", for example, the
     * transformer which transforms a rsf file into a sil file is named
     * "RSF2SIL". If the transformer name is included in the transfomers vector,
     * locate the transformer class in the unitrans package. If the transformer
     * name is not included in the vector, locate the transformer class
     * implemented by the user. If the input file format is the same as the
     * output format, no transformation occurs.
     *
     * @param in
     *            The input file.
     * @param out
     *            The output file.
     * @throws Exception
     */
    public void transformTwoFiles(String in, String out) throws Exception {
        try
        {
            // Extract input format and output format
            String in_format = in.substring(in.lastIndexOf(".") + 1);
            String out_format = out.substring(out.lastIndexOf(".") + 1);

            /*
             * If the input file (in) has the same format as the output file
             * (out), no transformation occurs.
             */
            if (in_format.equalsIgnoreCase(out_format)) return;

            // Compose the transformer class name following the naming.
            String classname = null;
            String tranformer = in_format.toUpperCase() + "2" + out_format.toUpperCase();

            /*
             * If the transformer is included in the transformers vector, locate
             * the class in the unitrans package. Otherwise, locate the class
             * implemented by user.
             */
            if (transformers.contains(tranformer)) classname = "unitrans." + tranformer;
            else classname = tranformer;
            Class transformer = Class.forName(classname);
            Class[] parameterTypes = { Class.forName("java.lang.String"), Class.forName("java.lang.String") };
            Constructor c = transformer.getConstructor(parameterTypes);
            Object[] parameters = { in, out };
            Transformer t = (Transformer) c.newInstance(parameters);

            t.read_input();
            t.write_output();
        }
        /*
         * ClassNotFoundException is caused by the invocation of forName method.
         */
        catch (ClassNotFoundException e)
        {
            String err = "Transform " + in + " into " + out + ": ";
            err = err + "fail to find the transformer class!";
            throw new Exception(err, e);
        }
        /*
         * NoSuchMethodException is caused by the invocation of getConstructor
         * method.
         */
        catch (NoSuchMethodException e)
        {
            String err = "Transform " + in + " into " + out + ": ";
            err = err + "the transformer class does not have the correct constructor!";
            throw new Exception(err, e);
        }
        /*
         * IllegalAccessException, InstantiationException,
         * InvocationTargetException are caused by the invocation of newInstance
         * method.
         */
        catch (IllegalAccessException e)
        {
            String err = "Transform " + in + " into " + out + ": ";
            err = err + "fail to access the transformer constructor!";
            throw new Exception(err, e);
        }
        catch (InstantiationException e)
        {
            String err = "Transform " + in + " into " + out + ": ";
            err = err + "fail to instantiate a new transformer instance!";
            throw new Exception(err, e);
        }
        catch (InvocationTargetException e)
        {
            String err = "Transform " + in + " into " + out + ": ";
            err = err + "fail to invoke the transformer constructor!";
            throw new Exception(err, e);
        }
        // /*
        // * IOException is caused by the invocation
        // * of read_input method
        // */
        // catch (IOException e) {
        // String err = "Transform " + in + " into " + out + ": ";
        // err = err + "fail to read from " + in + " !";
        // throw new Exception(err, e);
        // }
        /*
         * RuntimeException includes NullPointerException, ClassCastException,
         * NoSuchElementException, IndexOutOfBoundsException.
         */
        catch (RuntimeException e)
        {
            String err = "Transform " + in + " into " + out + ": ";

            if (e instanceof NoSuchElementException) err = err + "fail to parse " + in + "!";

            if (e instanceof IndexOutOfBoundsException) err = err + "fail to parse " + in + "!";

            if (e instanceof ClassCastException) err = err + "the transformer class does not inherit the unitrans package!";

            throw new Exception(err, e);
        }
    }

    /**
     * Compare two decomposition files (file1, file2) using the selected
     * comparison method. The method class is named "method name" + "Method",
     * for example, the mojo method is named "MoJoMethod". The method name is
     * case sensitive. If the method name is included in the methods vector,
     * locate the method class in the comparisonmethod package. If the method
     * name is not included in the methods vector, locate the method class
     * implemented by the user.
     *
     * @param method
     *            The selected comparison method by the user.
     * @param file1
     *            The decomposition file1.
     * @param file2
     *            The decomposition file2.
     * @param options
     *            The comparison options.
     * @return The comparison result.
     * @throws Exception
     */
    public double compareTwoFiles(String method, String file1, String file2, String options) throws Exception {
        try
        {

            String classname = null;
            /*
             * If the method is included in the methods vector, locate the class
             * in the comparisonmethod package. Otherwise, locate the class
             * implemented by the user.
             */
            if (methods.contains(method)) classname = "comparisonmethod." + method + "Method";
            else classname = method + "Method";

            Class comparisonMethod = Class.forName(classname);
            Class[] parameterTypes = {};
            Constructor c = comparisonMethod.getConstructor(parameterTypes);
            Object[] parameters = {};
            ComparisonMethod cm = (ComparisonMethod) c.newInstance(parameters);

            return cm.compare(file1, file2, options);
        }
        /*
         * ClassNotFoundException is caused by the invocation of forName method.
         */
        catch (ClassNotFoundException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";
            err = err + "fail to find the " + method + "Method class!";
            throw new Exception(err, e);
        }
        /*
         * NoSuchMethodException is caused by the invocation of getConstructor
         * method.
         */
        catch (NoSuchMethodException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";
            err = err + "fail to find the method constructor!";
            throw new Exception(err, e);
        }
        /*
         * IllegalAccessException, InstantiationException,
         * InvocationTargetException are caused by the invocation of newInstance
         * method.
         */
        catch (IllegalAccessException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";
            err = err + "fail to access the method constructor!";
            throw new Exception(err, e);
        }
        catch (InstantiationException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";
            err = err + "fail to instantiate a method instance!";
            throw new Exception(err, e);
        }
        catch (InvocationTargetException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";
            err = err + "fail to invoke the method constructor!";
            throw new Exception(err, e);
        }
        /*
         * IOException is caused by the invocation of compare method
         */
        catch (IOException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";
            err = err + "fail to compare " + file1 + " " + file2 + "!";
            throw new Exception(err, e);
        }
        /*
         * RuntimeException includes NullPointerException, ClassCastException,
         * NumberFormatException.
         */
        catch (RuntimeException e)
        {
            String err = "Compare " + file1 + " " + file2 + ": ";

            if (e instanceof NumberFormatException) err = err + "error in comparing the two files!";

            if (e instanceof ClassCastException) err = err + "the method class does not implement the interface!";

            throw new Exception(err, e);
        }
    }

    /**
     * Weight a similarity vector by applying the selected weighting scheme. The
     * scheme class is named "scheme name" + "Scheme", for example, the first
     * element scheme is named "FirstElementScheme". The scheme name is case
     * sensitive. If the scheme name is included in the schemes vector, locate
     * the method class in the weightingscheme package. If the scheme name is
     * not included in the schemes vector, locate the scheme class implemented
     * by the user.
     *
     * @param scheme
     *            The weighting scheme selected by the user.
     * @param sv
     *            The similarity vector to be weighted.
     * @return The weighting result
     * @throws Exception
     */
    public double weightAVector(String scheme, Vector<Double> sv) throws Exception {

        try
        {
            String classname = null;
            /*
             * If the scheme is included in the schemes vector, locate the class
             * in the comparisonmethod package. Otherwise, locate the class
             * implemented by the user.
             */
            if (schemes.contains(scheme)) classname = "weightingscheme." + scheme + "Scheme";
            else classname = scheme + "Scheme";

            Class weightingScheme = Class.forName(classname);
            Class[] parameterTypes = {};
            Constructor c = weightingScheme.getConstructor(parameterTypes);
            Object[] parameters = {};
            WeightingScheme ws = (WeightingScheme) c.newInstance(parameters);

            return ws.weight(sv);
        }
        /*
         * ClassNotFoundException is caused by the invocation of forName method.
         */
        catch (ClassNotFoundException e)
        {
            String err = "Weight a vector: ";
            err = err + "fail to find the " + scheme + "Sheme class!";
            throw new Exception(err, e);
        }
        /*
         * NoSuchMethodException is caused by the invocation of getConstructor
         * method.
         */
        catch (NoSuchMethodException e)
        {
            String err = "Weight a vector: ";
            err = err + "fail to find the scheme constructor!";
            throw new Exception(err, e);
        }
        /*
         * IllegalAccessException, InstantiationException,
         * InvocationTargetException are caused by the invocation of newInstance
         * method.
         */
        catch (IllegalAccessException e)
        {
            String err = "Weight a vector: ";
            err = err + "fail to access the scheme constructor!";
            throw new Exception(err, e);
        }
        catch (InstantiationException e)
        {
            String err = "Weight a vector: ";
            err = err + "fail to instantiate a new scheme instance!";
            throw new Exception(err, e);
        }
        catch (InvocationTargetException e)
        {
            String err = "Weight a vector: ";
            err = err + "fail to invoke the scheme constructor!";
            throw new Exception(err, e);
        }
        /*
         * RuntimeException includes NullPointerException, ClassCastException,
         * IllegalArgumentException.
         */
        catch (RuntimeException e)
        {
            String err = "Weight a vector: ";

            if (e instanceof ClassCastException) err = err + "the scheme class does not implement the interface!";

            throw new Exception(err, e);
        }
    }

    /**
     * Creates and returns a tree representing the decomposition contained in
     * the given rsf file.
     *
     * @param rsf
     *            The file name of the given rsf file.
     * @return The tree represents the decomposition contained in the rsf file.
     * @throws Exception
     */
    public DefaultMutableTreeNode transformRSFToTree(String rsf) throws Exception {
        try
        {
            RSF2Tree rt = new RSF2Tree(rsf);
            return rt.rsf2tree();
        }
        catch (IOException e)
        {
            String err = "Transform " + rsf + " into a tree: ";
            err = err + "fail to open " + rsf + " for reading or read from " + rsf + "!";
            throw new Exception(err, e);
        }
        catch (RuntimeException e)
        {
            String err = "Transform " + rsf + " into a tree: ";

            if (e instanceof NoSuchElementException) err = err + " fail to parse " + rsf + "!";

            if (e instanceof IllegalArgumentException) err = err + rsf + " may have a circle!";

            throw new Exception(err, e);
        }
    }

    /**
     * Creates and returns a rsf file representing the decomposition contained
     * in the given tree.
     *
     * @param tree
     *            The decomposition tree.
     * @return Return the rsf file represents the decomposition contained in the
     *         given decomposition tree.
     * @throws Exception
     */
    public String transformTreeToRSF(DefaultMutableTreeNode tree) throws Exception {
        try
        {
            Tree2RSF tr = new Tree2RSF(tree);
            return tr.tree2rsf();
        }
        catch (IOException e)
        {
            String err = "Transform the tree to a rsf: ";
            err = err + "fail to open " + tree.getUserObject() + " for writing!";
            throw new Exception(err, e);
        }
        catch (RuntimeException e)
        {
            String err = "Transform the tree to a rsf: ";
            throw new Exception(err, e);
        }
    }

    /**
     * Creates and returns the nested decomposition vector of a detailed flat
     * decomposition trees. Each tree represents the decomposition of a certain
     * level in the original decomposition. In a decomposition tree, an internal
     * node is denoted as a cluster; a leaf is denoted as an object whose parent
     * is a cluster; a level is the length from the root to a cluster. All the
     * clusters in the tree can be divided into levels.
     *
     * @param root
     *            The root of a tree represents a nested decomposition.
     * @return The nested decomposition vector of the nested decomposition, each
     *         element of the vector is a tree which is a detailed flat
     *         decomposition of a level in the original decomposition.
     */
    public Vector<DefaultMutableTreeNode> getNDV(DefaultMutableTreeNode root) {

        Vector<DefaultMutableTreeNode> result = null;

        /*
         * If the tree is null, null is returned.
         */
        if (root == null) return result;

        // The total number of levels.
        int numLevels = root.getDepth() - 1;

        /*
         * If the tree has less than 1 level, null is returned.
         */
        if (numLevels < 1) return result;

        /*
         * Only tree with more than 1 level can have a NDV.
         */
        result = new Vector<DefaultMutableTreeNode>();

        /*
         * The decomposition tree only contains one level of clusters, then it
         * is already a detailed flat decomposition.
         */
        if (numLevels == 1)
        {
            result.add(root);
            return result;
        }

        /*
         * Vector levels is a vector which contains all the levels in the
         * decomposition tree each of which is a vector that contains all the
         * clusters with the same height. For each level, constrcut a detail
         * flat decomposition tree called levelTree.
         */
        for (int i = 0; i < numLevels; i++)
        {
            // Clone a new tree for the current level.
            DefaultMutableTreeNode levelTree = cloneTree(root);
            Vector<Vector<DefaultMutableTreeNode>> levels = getLevels(levelTree);
            // The current level.
            Vector<DefaultMutableTreeNode> level = levels.elementAt(i);
            int currentLevel = i + 1;

            /*
             * Step 1: each object whose cluster belongs to the level that
             * larger than the current level is assigned to its ancestor cluster
             * in the current level.
             */

            /*
             * For each cluster of the current level: 1. Remove the child that
             * is a cluster. 2. Add all the object descendants to this cluster
             * as its children.
             */
            Iterator<DefaultMutableTreeNode> nodes = level.iterator();
            while (nodes.hasNext())
            {
                DefaultMutableTreeNode node = nodes.next();
                Vector<DefaultMutableTreeNode> descendants = getDescendants(levelTree, node);

                // 1. Remove the child that is a cluster.
                DefaultMutableTreeNode child = (DefaultMutableTreeNode) node.getFirstChild();
                while (child != null)
                {
                    if (child.isLeaf())
                    {
                        child = child.getNextSibling();
                    }
                    else
                    {
                        DefaultMutableTreeNode removal = child;
                        child = child.getNextSibling();
                        node.remove(removal);
                    }
                }
                // 2. Add all the object descendants to this cluster as its
                // children.
                Iterator<DefaultMutableTreeNode> di = descendants.iterator();
                while (di.hasNext())
                {
                    DefaultMutableTreeNode descendant = di.next();
                    if (!node.isNodeChild(descendant))
                    {
                        descendant.removeFromParent();
                        node.add(descendant);
                    }
                }
            }

            /*
             * Step 2: Convert the levelTree to a detailed flat decomposition:
             * Any cluster that contains at least one object in the original
             * decomposition is assigned directly to the root.
             */

            /*
             * The levelTree of the top level is already a detailed
             * decomposition, no need to be converted.
             */
            if (i != 0)
            {
                levels = getLevels(levelTree);
                /*
                 * Start from the bottom level of the levelTree, remove each
                 * cluster of the bottom level from its parent and add to the
                 * root. Then examine its parent level, since the bottom level
                 * has been removed, if a cluster of the parent level does not
                 * have any object, the cluster will become an object, in such
                 * case remove this cluster; if the cluster has some object,
                 * after the bottom level removed, it is still a cluster, remove
                 * it from its parent and add it to the root.
                 */
                for (int j = currentLevel - 1; j >= 0; j--)
                {
                    Vector<DefaultMutableTreeNode> v = levels.elementAt(j);
                    Iterator<DefaultMutableTreeNode> ni = v.iterator();
                    while (ni.hasNext())
                    {
                        DefaultMutableTreeNode n = (DefaultMutableTreeNode) ni.next();
                        n.removeFromParent();
                        if (!n.isLeaf()) levelTree.add(n);
                    }
                }
            }
            // Add the levelTree to the result.
            result.add(levelTree);
        }
        return result;
    }

    /**
     * Create and return a vector which classifies all the clusters into levels
     * based on their height in the decomposition tree. Each level is a vector
     * that contains all the clusters with the same height. If the levels vector
     * is empty, the tree only contains the root. O(2N)
     *
     * @param root
     *            The root of a decomposition tree.
     * @return The vector each element of which is a vector which contains all
     *         the clusters with the same height.
     */
    @SuppressWarnings( { "unchecked", "unchecked" })
    private Vector<Vector<DefaultMutableTreeNode>> getLevels(DefaultMutableTreeNode root) {

        Vector<Vector<DefaultMutableTreeNode>> levels = new Vector<Vector<DefaultMutableTreeNode>>();

        // Add the first level into the levels vector.
        Vector<DefaultMutableTreeNode> level1 = new Vector<DefaultMutableTreeNode>();
        Enumeration level1Nodes = root.children();
        while (level1Nodes.hasMoreElements())
        {
            DefaultMutableTreeNode node = (DefaultMutableTreeNode) level1Nodes.nextElement();
            if (!node.isLeaf()) level1.add(node);
        }
        // If the tree contains only the root, the levels is empty.
        if (!level1.isEmpty()) levels.add(level1);

        // Add the remaining levels into the levels vector.
        while (!levels.isEmpty())
        {
            Vector<DefaultMutableTreeNode> level = new Vector<DefaultMutableTreeNode>();
            // The previous level added into the levels vector.
            Vector<DefaultMutableTreeNode> previousLevel = levels.lastElement();
            Iterator<DefaultMutableTreeNode> nodes = previousLevel.iterator();

            /*
             * Based on the previous level, construct the current level: For
             * each cluster in the previous level, examine its children and add
             * the child which is a cluster into the current level vector.
             */
            while (nodes.hasNext())
            {
                DefaultMutableTreeNode node = nodes.next();
                Enumeration children = node.children();
                while (children.hasMoreElements())
                {
                    DefaultMutableTreeNode child = (DefaultMutableTreeNode) children.nextElement();
                    if (!child.isLeaf()) level.add(child);
                }
            }
            // The previous level is the bottom level.
            // All its children are objects.
            if (level.isEmpty()) break;

            // Add the current level into the levels vector.
            levels.add(level);
        }
        return levels;
    }

    /**
     * Creates and returns a vector containing all the objects of a
     * decomposition tree. O(N)
     *
     * @param root
     *            The root of a decomposition tree.
     * @return Returns a vector all the objects in the tree.
     */
    @SuppressWarnings("unchecked")
    private Vector<DefaultMutableTreeNode> getObjects(DefaultMutableTreeNode root) {
        Vector<DefaultMutableTreeNode> result = new Vector<DefaultMutableTreeNode>();
        Enumeration nodes = root.depthFirstEnumeration();
        while (nodes.hasMoreElements())
        {
            DefaultMutableTreeNode node = (DefaultMutableTreeNode) nodes.nextElement();
            if (node.isLeaf()) result.add(node);
        }
        return result;
    }

    /**
     * Creates and returns a hashtable that stores all the leaf descendents of
     * the level: key: the internal node of the level value: a vector containing
     * all the leaf descendents of this node
     *
     * @param root
     *            the root of a tree
     * @param level
     *            the vector that contains all the internal node with the same
     *            height
     * @return a hashtable contains all the leaf descendents of the nodes of the
     *         level
     */
    @SuppressWarnings("unchecked")
    private Vector<DefaultMutableTreeNode> getDescendants(DefaultMutableTreeNode root, DefaultMutableTreeNode node) {
        Vector<DefaultMutableTreeNode> result = new Vector<DefaultMutableTreeNode>();
        Iterator<DefaultMutableTreeNode> descendants = getObjects(root).iterator();
        while (descendants.hasNext())
        {
            DefaultMutableTreeNode descendant = (DefaultMutableTreeNode) descendants.next();
            if (node.isNodeDescendant(descendant)) result.add(descendant);
        }
        return result;
    }

    /**
     * Clones a decomposition tree with the same structure and user objects.
     * O(N)
     *
     * @param root
     *            The root of a decomposition tree.
     * @return A clone of the decomposition tree.
     */
    private DefaultMutableTreeNode cloneTree(DefaultMutableTreeNode root) {
        DefaultMutableTreeNode result = (DefaultMutableTreeNode) root.clone();
        Enumeration children = root.children();
        while (children.hasMoreElements())
        {
            DefaultMutableTreeNode child = (DefaultMutableTreeNode) children.nextElement();
            result.add(cloneTree(child));
        }
        return result;
    }

}